A Fenwick tree (also known as binary indexed tree) is a data structure that can be used to implement cumulative frequency tables. It was invented by Peter Fenwick in 1994. [1]
Contents |
A Fenwick tree is a tree that is indexed by the bits of the key for that tree. This tree can only be implemented for keys that are integers and have a fixed range.
Fenwick trees are typically implemented as arrays.
Fenwick trees are used to implement the arithmetic coding algorithm, so the operations it supports are guided primarily by the use that it will be put to in the application above.
They can also be used to compute the sum of ranges of consecutive elements in O(log n) time. With the store (or update) operation taking the same O(log n) time.
Fenwick tree supports the following basic operations each of which take O(log n) time:
It also supports scaling all frequencies in the entire tree by a constant factor in O(n) time.
|
||||||||||||||||||||||||||